package com.zlsy.learning.leetcode.arraycorrelation.array1010;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhouliang
 * @date 2020/5/25 10:22
 * 给你一个int数组，要求其中元素两两组成一个组对60取模等于0，计算这个int数组有多少组符合规则，说明：其中1组合2，和2组合1算一种组合方式。
 */
public class NumPairsDivisibleBy60 {

    /**
     * 大数组直接运行超时
     * 时间复杂度：平方阶O(n²)
     */
    private static int numPairsDivisibleBy60(int[] time) {

        Map<Integer, Integer> map = new HashMap<>(time.length);
        for (int i = 0; i < time.length; i++) {
            int value = time[i];
            map.put(i, value);
        }

        Map<String, String> mapReal = new HashMap<>(16);
        for (Map.Entry<Integer, Integer> next : map.entrySet()) {
            Integer key = next.getKey();
            Integer value = next.getValue();
            for (int i = 0; i < time.length; i++) {
                if (!key.equals(i)) {
                    Integer b = map.get(i);
                    if ((value + b) % 60 == 0) {
                        String k = key + ":" + value + ":" + i + ":" + b;
                        String v = i + ":" + b + ":" + key + ":" + value;
                        mapReal.put(k, v);
                    }
                }
            }
        }

        return mapReal.size() / 2;
    }

    /**
     * 上面代码的简化：但是时间复杂度仍然是平方阶O(n²)
     * 大数组直接运行超时
     * 时间复杂度：平方阶O(n²)
     */
    private static int numPairsDivisibleBy601(int[] time) {
        int result = 0;
        for (int i = 0; i < time.length; i++) {
            for (int j = i + 1; j < time.length; j++) {
                if ((time[i] + time[j]) % 60 == 0) {
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * 最优解
     * 首先我们得弄清楚，一个随机的int数组里面的元素量量组合且模60为0的，
     * 那么这个两两符合规则的元素，对60单独取模的和要么就是等于0，要么就加起来等于60
     * 我们可以先找出两个比较特殊的：0和30，0必须同余数也为0的组成CP，30也是必须同余数为30的组成CP
     * 其余剩下的就是模出来为1-59的。
     * 1-59
     * 2-58
     * ...
     * ...
     * ...
     * 29-31
     * 例如：
     * 模为1的和模为59的组合数量：index[1]=3;index[59]=2，那么就是 3*2=6种组合
     * 模为0的自己内部自己组合的数量：index[0]=6，那么组合方式：6*(6-1)/2
     */
    private static int numPairsDivisibleBy602(int[] time) {
        int count = 0;
        //空间复杂度 O(1)固定60
        int[] seconds = new int[60];
        //时间复杂度：O(n)
        for (int t : time) {
            //整数对60取模，可能有60种余数。故初始化一个长度为60的数组，统计各余数出现的次数。
            seconds[t % 60] += 1;
        }
        //余数为30的情况，只能同余数为0的组成CP，
        count += combination(seconds[30]);
        //余数为0的情况，只能同余数为0的组成CP，
        count += combination(seconds[0]);
        int i = 1, j = 59;
        while (i < j) {
            count += seconds[i++] * seconds[j--];
        }
        return count;
    }

    /**
     * 求组合数
     *
     * @param n 某个余数出现的次数
     * @return int 组合的方式数量
     */
    private static int combination(int n) {
        return n * (n - 1) / 2;
    }


    public static void main(String[] args) {
        int[] num = new int[]{30, 20, 150, 100, 40};
//        int[] num = new int[]{60, 60, 60};
        int i = numPairsDivisibleBy602(num);
        System.out.println(i);
    }
}
